package zuochengyun;

public class Trie {

	class TrieNode{
		//path表示有多少个单词共用这个结点
		public int path;
		//end表示有多少个单词以这个结点结尾
		public int end;
		public TrieNode[] map;
		
		public TrieNode() {
			path = 0;
			end = 0;
			//这里假定只包含26个字母的
			map = new TrieNode[26];
		}
	}
	
	
	public TrieNode root;
	public Trie(){
		root = new TrieNode();
	}
	
	/**
	 * 插入一个单词
	 * @param word
	 */
	public void insert(String word){
		if(word == null){
			return;
		}
		char[] chars = word.toCharArray();
		TrieNode node = root;
		int index = 0;
		for (int i = 0; i < chars.length; i++) {
			index = chars[i] - 'a';
			//如果该结点不存在，就新建一个
			if(node.map[index] == null){
				node.map[index] = new TrieNode();
			}
			node = node.map[index];
			node.path++;
		}
		node.end++;
	}
	
	/**
	 *删除该单词 
	 */
	public void delete(String word){
		//通过这一步，确保在该字典树中
		if(!search(word)){
			return;
		}
		char[] chars = word.toCharArray();
		TrieNode node = root;
		int index = 0;
		for (int i = 0; i < chars.length; i++) {
			index = chars[i] - 'a';
			//如果为1，又由于一定在该字典树中，所以直接置为null即可
			if(node.map[index].path-- == 1){
				node.map[index] = null;
				return;
			}
			node = node.map[index];
		}
		node.end--;
	}
	
	/**
	 * 判断该单词是否在该字典树中
	 * @param word
	 * @return
	 */
	public boolean search(String word){
		if(word == null){
			return false;
		}
		char[] chars = word.toCharArray();
		TrieNode node = root;
		int index = 0;
		for (int i = 0; i < chars.length; i++) {
			index = chars[i] - 'a';
			//如果该结点不存在，就新建一个
			if(node.map[index] == null){
				return false;
			}
			node = node.map[index];
		}
		//为什么不直接这样子返回呢? 可能是会有endw等于0(表示没有以它结尾的)
//		return true;
		return node.end != 0;
	}
	
	/**
	 * 返回以word为前缀的字符串的个数
	 * @param pre
	 * @return
	 */
	public int prefixNumber(String pre){
		if(pre == null){
			return 0;
		}
		char[] chars = pre.toCharArray();
		TrieNode node = root;
		int index = 0;
		for (int i = 0; i < chars.length; i++) {
			index = chars[i] - 'a';
			//如果该结点不存在，就新建一个
			if(node.map[index] == null){
				return 0;
			}
			node = node.map[index];
		}
		return node.path;
	}
	
	public static void main(String[] args) {
		Trie object = new Trie();
		String str1 = "abbbcd";
		String str2 = "abbbce";
		String str3 = "abbbcef";
		String str4 = "acbbcf";
		object.insert(str1);
		object.insert(str2);
		object.insert(str3);
		object.insert(str4);
		System.out.println(object.search(str1));
		System.out.println(object.search(str2));
		System.out.println(object.search(str3));
		System.out.println(object.search(str4));
		
		
		System.out.println(object.prefixNumber("abbbc"));
		System.out.println(object.prefixNumber("acbb"));
		
		object.delete(str3);
		object.delete(str4);
		
		System.out.println(object.prefixNumber("abbbc"));
		System.out.println(object.prefixNumber("acbb"));
	}
	
}
